UVa/11663 - GrayInc/11663.3.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 bool zeros[1005];
  28
  29 void prevify(string &s, int i);
  30
  31 void nextify(string &s, int i) {
  32     int n = s.size() - i;
  33     if (n == 0) return;
  34     if (n == 1) s[i] = s[i] == '0' ? '1' : '0';
  35     else {
  36         assert(n >= 2);
  37         if (s[i] == '1' and zeros[i+1]) s[i] = '0'; // 100000000
  38         else if (s[i] == '0' and s[i+1] == '1' and zeros[i+2]) s[i] = '1'; // 010000000
  39         else if (s[i] == '0') nextify(s, i + 1);
  40         else if (s[i] == '1') prevify(s, i + 1);
  41         else assert(false);
  42     }
  43 }
  44
  45 void prevify(string &s, int i) {
  46     int n = s.size() - i;
  47     if (n == 0) return;
  48     if (n == 1) s[i] = s[i] == '0' ? '1' : '0';
  49     else {
  50         assert(n >= 2);
  51         if (zeros[i]) s[i] = '1'; // 0000000000
  52         else if (s[i] == '1' and s[i+1] == '1' and zeros[i+2]) s[i] = '0'; // 11000000
  53         else if (s[i] == '0') prevify(s, i + 1);
  54         else if (s[i] == '1') nextify(s, i + 1);
  55         else assert(false);
  56     }
  57 }
  58
  59 int main(){
  60     int m;
  61     string s;
  62     while (cin >> m >> s) {
  63         if (m == 0 and s == "0") break;
  64         int n = s.size();
  65         while (m--) {
  66             zeros[n] = true;
  67             for (int i = n - 1; i >= 0; --i) {
  68                 zeros[i] = zeros[i + 1] and s[i] == '0';
  69             }
  70             nextify(s, 0);
  71         }
  72         cout << s << endl;
  73     }
  74
  75     return 0;
  76 }